use std::ptr::NonNull;
const QUEUE_NULL: Option<NonNull<()>> = None;
type QueueValue = Option<NonNull<()>>;
struct QueueEntry {
    data: QueueValue,
    prev: Option<NonNull<QueueEntry>>,
    next: Option<NonNull<QueueEntry>>,
}
struct Queue {
    head: Option<NonNull<QueueEntry>>,
    tail: Option<NonNull<QueueEntry>>,
}
fn queue_new() -> Option<Box<Queue>> {
    let queue = Box::new(Queue {
        head: None,
        tail: None,
    });
    if queue.is_null() {
        None
    } else {
        Some(queue)
    }
}
fn queue_free(queue: Box<Queue>) {
    let mut queue = Box::into_raw(queue);
    while !queue_is_empty(unsafe { &*queue }) {
        queue_pop_head(unsafe { &mut *queue });
    }
    unsafe {
        Box::from_raw(queue);
    }
}
fn queue_push_head(queue: &mut Queue, data: QueueValue) -> bool {
    use std::mem;
    use std::ptr::NonNull;
    let new_entry = Box::into_raw(Box::new(QueueEntry {
        data,
        prev: None,
        next: queue.head,
    }));
    unsafe {
        if new_entry.is_null() {
            return false;
        }
        if let Some(head) = queue.head {
            (*head.as_ptr()).prev = Some(NonNull::new(new_entry).unwrap());
        } else {
            queue.tail = Some(NonNull::new(new_entry).unwrap());
        }
        queue.head = Some(NonNull::new(new_entry).unwrap());
        return true;
    }
}
fn queue_pop_head(queue: &mut Queue) -> QueueValue {
    if unsafe { queue_is_empty(queue) } {
        return None;
    }
    let entry = queue.head.take().unwrap();
    queue.head = unsafe { entry.as_ref().next };
    let result = unsafe { entry.as_ref().data };
    if queue.head.is_none() {
        queue.tail = None;
    } else {
        queue.head.unwrap().as_mut().prev = None;
    }
    unsafe {
        libc::free(entry.as_ptr() as *mut libc::c_void);
    }
    result
}
fn queue_peek_head(queue: &Queue) -> QueueValue {
    if queue_is_empty(queue) {
        return None;
    } else {
        queue.head.map(|node| unsafe { node.as_ref().data })
    }
}
fn queue_push_tail(queue: &mut Queue, data: QueueValue) -> i32 {
    let new_entry = Box::into_raw(Box::new(QueueEntry {
        data,
        prev: None,
        next: None,
    }));
    let new_entry = unsafe { NonNull::new(new_entry) };
    if let Some(new_entry) = new_entry {
        let new_entry_ptr = new_entry.as_ptr();
        unsafe {
            (*new_entry_ptr).prev = queue.tail;
            if let Some(tail) = queue.tail {
                (*tail.as_ptr()).next = Some(new_entry);
            } else {
                queue.head = Some(new_entry);
            }
            queue.tail = Some(new_entry);
        }
        1
    } else {
        0
    }
}
fn queue_pop_tail(queue: &mut Queue) -> QueueValue {
    if queue_is_empty(queue) {
        return None;
    }
    let mut entry;
    let result;
    unsafe {
        entry = queue.tail.unwrap();
        queue.tail = (*entry).prev;
        result = (*entry).data;
        if let Some(tail) = queue.tail {
            (*tail).next = None;
        } else {
            queue.head = None;
        }
        Box::from_raw(entry);
    }
    result
}
fn queue_peek_tail(queue: &Queue) -> QueueValue {
    if queue_is_empty(queue) {
        QUEUE_NULL
    } else {
        queue
            .tail
            .map(|tail| unsafe { tail.as_ref().data })
            .unwrap()
    }
}
fn queue_is_empty(queue: &Queue) -> bool {
    queue.head.is_none()
}
